#include <iostream>
#include <vector>
using namespace std;

//哈希表：O(n)
//排序：下标为[n/2]（向下取整）：O(nlogn)
//分治法：O(nlogn)
int countElement(vector<int>& nums, int num, int l, int r);
int majorityElement(vector<int>& nums);
int findMajorityElement(vector<int>& nums);

int countElement(vector<int>& nums, int num, int l, int r) {
    int count = 0;
    for (unsigned int i = l; i <= r; i++) {
        if (nums[i] == num)
            count += 1;
    }
    return count;
}
int findMajorityElement(vector<int>& nums, int l, int r) {
    if (l == r)
        return nums[l];
    int mid = (l + r) / 2;
    int a = findMajorityElement(nums, l, mid);
    int b = findMajorityElement(nums, mid + 1, r);
    if (a == b)
        return a;
    
    int counta = countElement(nums, a, l, r);
    int countb = countElement(nums, b, l, r);
    if (counta > countb)
        return a;
    else 
        return b;
}

int majorityElement(vector<int>& nums) {
    return findMajorityElement(nums, 0, nums.size() - 1);
}

int main(){
    vector<int> nums = {6, 5, 5};
    cout << majorityElement(nums) << endl;
    return 0;
}